Subgraph complementation and minimum rank
Chrise Purcell

Abstract

Any graph G can be constructed by performing a sequence of subgraph 
complementations on the null graph with |G| vertices. We denote the 
shortest length of such a sequence by c_2(G). This invariant turns out 
to have many equivalent formulations and a close connection with the 
minimum rank of a graph (over F_2); that is, the minimum rank of a 
matrix whose off-diagonal zero entries are precisely the same as the 
adjacency matrix of a given graph. In particular, our results include 
that the two invariants differ by at most 1 and coincide for graphs 
whose min rank is odd; by considering tripartite complementations, we 
obtain a complete characterization of min rank in terms of 
complementations. We also show that the class of graphs G with c_2(G) at 
most k, which is hereditary, is finitely defined, and give a minimal 
forbidden induced subgraph characterisation when k=2.

(joint work with Calum Buchanan and Puck Rombach)